package NodeList;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class detectCycle {
    public ListNode detectCycle(ListNode head) {
//        ListNode node = head;
//        Set<ListNode> set = new HashSet<ListNode>();
//        while (node != null) {
//            if (set.contains(node)){
//                return node;
//            }
//            set.add(node);
//            node = node.next;
//        }
//        return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                ListNode temp1 = head;
                ListNode temp2 = fast;
                while (temp1 != temp2){
                    temp1 = temp1.next;
                    temp2 = temp2.next;
                }
                return temp1;
            }
        }
        return null;
    }
}
